package com.leetcode.二叉树.广度优先.迭代遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Iteration {
	
	//二维加过收集，，一个维度是在第几层，另一个维度是某一层的结果
	public List<List<Integer>> levelOrder(TreeNode root){
		//二维结果容器
		List<List<Integer>> resList = new ArrayList<List<Integer>>();
		Queue<TreeNode> que = new LinkedList<>();//队列
		if(root != null) que.offer(root);//入队(在队尾)
		while(!que.isEmpty()) {
			int len = que.size();//当前层数的节点数
			List<Integer> result = new ArrayList<Integer>();//添加放该层的结果容器（一维）
			while(len > 0) {
				TreeNode node = que.poll();//出队（在队头）
				result.add(node.val);
				//左右子树入队
				if(node.left != null) que.offer(node.left);
				if(node.right != null) que.offer(node.right);
				len--;
			}
			resList.add(result);
		}
		return resList;
	}
	
	//一维结果收集
	public List<Integer> levelOrder1(TreeNode root){
		//一维结果容器
		List<Integer> list = new ArrayList<Integer>();
		Queue<TreeNode> que = new LinkedList<>();//队列
		que.offer(root);//入队(在队尾)
		while(!que.isEmpty()) {
			TreeNode node = que.poll();//出队（在队头）
			list.add(node.val);
			//左右子树入队
			if(node.left != null) que.offer(node.left);
			if(node.right != null) que.offer(node.right);
		}
		return list;
	}
}

//树的定义
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode() {
	}

	TreeNode(int val) {
		this.val = val;
	}

	TreeNode(int val, TreeNode left, TreeNode right) {
		this.val = val;
		this.left = left;
		this.right = right;
	}
}